//题目:
// 基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。
// 假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
// 例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。
// 另有一个基因库bank记录了所有有效的基因变化,只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）
// 给你两个基因序列start和end以及一个基因库bank请你找出并返回能够使start变化为end所需的最少变化次数。
//如果无法完成此基因变化，返回 -1 。
// 注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。
#include<iostream>
#include<queue>
#include<unordered_map>

using namespace std;
//代码:
class Solution 
{
public:
    bool is_diff_one(const string& str1,const string str2)
    {
        int cnt=0;
        for(int i=0;i<str1.size();i++)
            if(str1[i]!=str2[i])
                cnt++;
        return cnt==1?true:false;
    }
    int minMutation(string startGene, string endGene, vector<string>& bank) 
    {
        //找到与start仅相差一个字符的所有str,在找与str仅相差一个字符(start除外)的所有str，直到找到end
        int step=0;
        //1.创建一个存放与start仅相差一个字符的所有str的容器
        queue<string> q;
        q.push(startGene);

        //2.创建一个哈希表，用于表征bank中的str是否被“寻到过”
        unordered_map<string,bool> hash;
        for(const auto& str:bank)hash[str]=false;
        hash[startGene]=true;

        //3.逐层寻找与start仅相差一个字符的所有str
        while(!q.empty())
        {
            step++;
            int size=q.size();
            for(int i=0;i<size;i++)
            {
                string s=q.front();
                //层出
                q.pop();
                //层入
                for(const auto& str:bank)
                {
                    if(hash[str]==false && is_diff_one(s,str))
                    {
                        //注意：这里就表示已经找到了
                        if(str==endGene)return step;

                        q.push(str);
                        hash[str]=true;//标识入队列的str的状态
                    }
                }
            }
        }
        return -1;
    }
};